class Solution {
public:
    /**
     * @param pattern: a string, denote pattern string
     * @param teststr: a string, denote matching string
     * @return: an boolean, denote whether the pattern string and the matching string match or not
     */
     
    // 法一：个 两边都映射一遍
    // bool wordPattern(string &pattern, string &teststr) {
    //     map<char, string> record_map;
    //     map<string, char> reverse_record_map;
    //     vector<string> new_str;
    //     int pos = 0;
    //     while (pos < teststr.size())
    //     {
    //         // int next_pos = teststr.find(pos, ' '); 18446744073709551615
    //         int next_pos = teststr.find(' ', pos);
    //         if (next_pos == -1) next_pos = teststr.size();
    //         // new_str.push_back(teststr.substr(pos, next_pos));
    //         new_str.push_back(teststr.substr(pos, next_pos - pos));
    //         pos = next_pos + 1;
    //     }
    //     for (int i = 0; i < new_str.size(); ++i)
    //     {
    //         if (record_map.find(pattern[i]) == record_map.end()) 
    //             record_map[pattern[i]] = new_str[i];
    //         else if (record_map[pattern[i]] != new_str[i]) return false;
    //         // "abba"
    //         // "dog dog dog dog" 倒过来还要映射一遍
            
    //         if (reverse_record_map.find(new_str[i]) == reverse_record_map.end()) 
    //             reverse_record_map[new_str[i]] = pattern[i];
    //         else if (reverse_record_map[new_str[i]] != pattern[i]) return false;
    //     }
    //     return true;
    // }

    // 法二：patter map和str map编号保持一致    
    bool wordPattern(string &pattern, string &teststr) {
        map<char, int> pattern_map;
        map<string, int> str_map;
        string tmp = ""; // 注意c++中的split实现还是这样用指针比较好
        teststr += ' '; //最后加一个
        int pos = 0;
        int i = 0;
        while (pos < teststr.length())
        {
            if (teststr[pos] == ' ')
            {
                if (pattern_map.find(pattern[i]) == pattern_map.end() 
                && str_map.find(tmp) == str_map.end())
                {
                    pattern_map[pattern[i]] = pos;
                    str_map[tmp] = pos;
                }
                else if (pattern_map.find(pattern[i]) != pattern_map.end() 
                && str_map.find(tmp) != str_map.end())
                {
                    // return pattern_map[pattern[i]] == str_map[tmp]; 注意！
                    if (pattern_map[pattern[i]] != str_map[tmp]) return false;
                }
                else return false;
                i++;
                pos++;
                tmp = ""; // 注意恢复
            }
            else
            {
                tmp += teststr[pos++];
            }
        }
        return true;
    }
};